package algorithm.linkedlist;

import algorithm.model.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode : https://leetcode.com/problems/linked-list-cycle/description/
 * Difficulty : Easy
 *
 * 给一个单向链表，判断这个链表是否有环
 *
 * 两种方法
 * 1）用一个Set保存已遍历过的链表，往里面add失败的话，就说明遇有环，返回true.
 * 否则将会在O(N)时间内遍历完成，返回false
 *
 * 2）设定两个指针，两个指针步长不同，依次向前移动，如果指针相遇，那么说明有环存在。
 * 注意，步长的差需要为素数。
 * @Author Antony
 * @Since 2018/7/16 11:40
 */
public class LinkedListCycle {

    // beats 12.38% - 5ms
    public boolean hasCycle_set(ListNode head) {
        Set<ListNode> nodeSet = new HashSet<>();
        while(head != null){
            if(!nodeSet.add(head)) return true;
            head = head.next;
        }

        return false;
    }


    // beats 100.0% - 0ms
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && slow != null){
            if(fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }

        return false;
    }
}
